package com.zhanghp.class038;

import java.util.HashSet;
import java.util.Set;

/**
 * O(2^n * n) <br/>
 * 复杂度计算<br/>
 * 如： a             b              c    <br/>
 *     要0个a和1个a两种情况去递归
 *                  走到b时：0个b/1个b去递归
 *                                  ....
 *    包含/不包含     包含/不包含       包含/不包含<br/>
 *    每个都有2种情况 一共有 2^n结果个 <br/>
 *    每个结果都要遍历一遍，平均复杂度O(n) <br/>
 *    所以 为 O(2^n * n)
 */
// 字符串的全部子序列
// 子序列本身是可以有重复的，只是这个题目要求去重
// 测试链接 : https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a
public class Code01_Subsequences {

    public static String[] convert(Set<String> set) {

        String[] strArr = new String[set.size()];
        int i = 0;
        for (String it : set) {
            strArr[i++] = it;
        }
        // 第2种方式
        // String[] array = set.toArray(new String[set.size()]);
        return strArr;
    }

    // ================================== 解法1 =======================================

    public static String[] generatePermutation1(String str) {

        /**
         * ==============参数准备==============
         */
        // 字符数组
        char[] charArray = str.toCharArray();
        // 收集路径集合
        Set<String> set = new HashSet<>();
        // 路径收集器
        StringBuilder path = new StringBuilder();

        /**
         * =============带路径递归==============
         */
        f(charArray, 0, path, set);


        /**
         *  =============结果返回==============
         */
        return convert(set);
    }

    public static void f(char[] charArray, int i, StringBuilder path, Set<String> set) {
        // 达到节点末尾判断，添加set
        if (i == charArray.length) {
            set.add(path.toString());
        } else {
            // 1.添加   - 节点
            path.append(charArray[i]);
            f(charArray, i + 1, path, set);
            // 2.不添加 - 节点
            path.deleteCharAt(path.length() - 1);
            f(charArray, i + 1, path, set);
        }

    }

    // ================================== 解法2 =======================================

    public static String[] generatePermutation2(String str) {
        char[] charArray = str.toCharArray();
         // 收集路径集合
        Set<String> set = new HashSet<>();

        /**
         * =============带路径递归==============
         */
        f(charArray, new char[charArray.length], 0, 0, set);


        /**
         *  =============结果返回==============
         */
        return convert(set);
    }

    /**
     * 默认使用0开头，覆盖值
     *
     * @param charArr
     * @param path
     * @param cur 当前值的charArr的索引 --》 当前要处理的字符
     * @param size 控制覆盖的位置 （包含，还是不包含的索引覆盖位置） & 添加路径字符数组的数量
     * @param set
     */
    public static void f(char[] charArr, char[] path, int cur, int size, Set<String> set) {
        if (cur == charArr.length) {
            set.add(String.valueOf(path, 0, size));
        } else {
            // 重置字符数组值 - 重复利用
            // 根据size索引（是否添加上一层的字符） 来被 填充/覆盖 当前size索引值
            path[size] = charArr[cur];
            // 1.添加   - 节点 (size + 1代表添加了当前层的字符)
            f(charArr, path, cur + 1, size + 1, set);
            // 2.不添加 - 节点 (size 代表不添加了当前层的字符)
            f(charArr, path, cur + 1, size, set);
        }
    }


}
